/*
 * @lc app=leetcode.cn id=35 lang=javascript
 *
 * [35] 搜索插入位置
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
  if (nums.indexOf(target) !== -1) {
    // 数组含有数值 就直接返回下标值
    return nums.indexOf(target);
  } else {
    // 数组不含有 就插入到相应的位置上 并返回插入位置的下标 如何快速找到插入位置 二分法试试看
    let first = 0, last = nums.length - 1, result = null;
    // 应该排除最小或者最大的情况
    if (target < nums[first] || target > nums[last]) {
      result = target < nums[first] ? first : last + 1;
      return result;
    }
    while (first < last) {
      let mid = Math.floor((first + last) / 2); // 中间下标
      if (target < nums[mid]) {
        // 前半部分
        last = mid;
      } else if (target > nums[mid]) {
        // 后半部分
        first = mid;
      }
      if (first + 1 === last) {
        result = first + 1;
        break;
      };
    }
    return result;
  }
};
// @lc code=end

